package problems.daily;

/**
 * 1043. 分隔数组以得到最大和
 *
 * @author dubulingbo, 2023-04-19, 019 9:33.
 */
public class DT1043 {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        // dp[i] 表示以 arr[i] 结尾分割的最大和
        int[] dp = new int[n];

//        for (int i = 1; i <= n; ++i) {
//            int max = arr[i - 1];
//            for (int j = i - 1; j >= 0 && j >= i - k; --j) {
//                dp[i] = Math.max(dp[i], dp[j] + max * (i - j));
//                if (j > 0) {
//                    max = Math.max(max, arr[j - 1]);
//                }
//            }
//        }

        // 当 i < k 时，分成一组即可获得最大的和
        int maxVal = 0;
        for (int i = 0; i < k; ++i) {
            maxVal = Math.max(maxVal, arr[i]);
            dp[i] = maxVal * (i + 1);
        }

        for (int i = k; i < n; ++i) {
            maxVal = arr[i];
            for (int j = i; j >= 0 && j > i - k; --j) {
                maxVal = Math.max(arr[j], maxVal);
                dp[i] = Math.max(dp[i], dp[j - 1] + (i - j + 1) * maxVal);
            }
        }

        return dp[n-1];
    }
}
